// 定长内存池的实现
// 功能描述：
// |||||||||||||||||||||||||||||||||||||||||    大块内存
// ||| -> ||| -> ||| -> ||| -> ||| -> ||| -> ||| -> ||| -> |||    还回来的内存块所链接的 内存链表

#include <iostream>
#include <vector>

#ifdef _WIN32
    #include <Windows.h>
#else
    // ...
#endif


// 内存链表：将头指针 指向下一个节点
void*& nextObj(void* ptr)
{
    return (*(void**)ptr);
}

// 直接从堆上按页申请内存空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
    void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
    // linux下为brk, mmap等
    void* ptr;
#endif
    if(ptr == nullptr)
        throw std::bad_alloc();
    return ptr;
}

template<class T>
class objectPool
{
private:
    char* _memory = nullptr;    // 指向大块内存的指针
    size_t _remainBytes = 0;    // 大块内存在被切分过程中的剩余字节数
    void* _freeList = nullptr;  // 换回来的内存块所进行链接的头指针
public:
    // 申请对象（内存块）【检查内存链表中是否有符合要求的内存小块，若符合则直接从内存链表中拿，若都不符合则切分大块内存，_remainByte减少】
    T* New()
    {
        T* obj = nullptr;
        // 1.优先将内存链表中的内存块，重复利用
        if(_freeList != nullptr)
        {
            // 从内存链表中头删一个内存小块
            obj = (T*)_freeList;
            _freeList = nextObj(_freeList);
        }
        else    // 2.内存链表中无内存块，只能从大块内存中切分了
        {
            // 3.保证内存块对象能够存储的下地址
            size_t objSize = sizeof(T)<sizeof(void*)?sizeof(void*):sizeof(T);   // 申请的至少字节数
            // 4. 剩余内存若不够时，则重新从堆上开辟空间
            if(_remainBytes < objSize)
            {
                _remainBytes = 128*1024;    // 默认一次性从堆上开辟 128*1024 字节空间
                _memory = (char*)SystemAlloc(_remainBytes >> 13);
                if(_memory == nullptr){
                    throw std::bad_alloc();
                }
            }
            // 5.此时已经申请空间完成
            obj = (T*)_memory;
            _memory += objSize;
            _remainBytes -= objSize;
        }
        // 6.定位new, 显示调用 T 的构造函数初始化
        new(obj)T;

        return obj;
    }
    // 释放对象
    void Delete(T* obj)
    {
        // 1.显示调用 T 的析构函数完成对象的数据清理
        obj->~T();
        // 2.将释放的对象头插到自由链表
        nextObj(obj) = _freeList;
        _freeList = obj;
    }

};
struct TreeNode
{
	int _val;
	TreeNode* _left;
	TreeNode* _right;
	TreeNode()
		:_val(0)
		, _left(nullptr)
		, _right(nullptr)
	{}
};


// 定长内存池的 Debug
// void TestObjectPool()
// {
// 	// 申请释放的轮次
// 	const size_t Rounds = 3;
// 	// 每轮申请释放多少次
// 	const size_t N = 1000000;
// 	std::vector<TreeNode*> v1;
// 	v1.reserve(N);

// 	//malloc和free
// 	size_t begin1 = clock();
// 	for (size_t j = 0; j < Rounds; ++j)
// 	{
// 		for (int i = 0; i < N; ++i)
// 		{
// 			v1.push_back(new TreeNode);
// 		}
// 		for (int i = 0; i < N; ++i)
// 		{
// 			delete v1[i];
// 		}
// 		v1.clear();
// 	}
// 	size_t end1 = clock();

// 	//定长内存池
// 	objectPool<TreeNode> TNPool;
// 	std::vector<TreeNode*> v2;
// 	v2.reserve(N);
// 	size_t begin2 = clock();
// 	for (size_t j = 0; j < Rounds; ++j)
// 	{
// 		for (int i = 0; i < N; ++i)
// 		{
// 			v2.push_back(TNPool.New());
// 		}
// 		for (int i = 0; i < N; ++i)
// 		{
// 			TNPool.Delete(v2[i]);
// 		}
// 		v2.clear();
// 	}
// 	size_t end2 = clock();

// 	std::cout << "new cost time:" << end1 - begin1 << std::endl;
// 	std::cout << "object pool cost time:" << end2 - begin2 << std::endl;
// }
